package main

import (
	"fmt"
	"time"
)

func main() {

	start := time.Now()
	num := 1000000 // 定义 100 万节点，节点值从 1 开始
	lastOneNum := -1
	for i := 1; i <= 10; i++ {
		head := InitYsfNode(num)
		lastOneNum = CalcLastOneEle(head, 3, 2)
	}
	//  lastOneNum 在循环中间我们暂时不输出
	// 根据网友反馈： 在循环中间做输出，输出命令本身可能会影响性能，所以最后只输出一次

	fmt.Println("lastOneNum：", lastOneNum)
	fmt.Printf("单次平均耗时：%d ms\n", time.Now().Sub(start).Milliseconds()/10)

}

// 定义环形节点
type YsfNode struct {
	Number int
	Next   *YsfNode
}

func InitYsfNode(n int) *YsfNode {
	//易错点：
	// head 头元素必须要单独创建，不能放在for循环，避免head节点跟着游标节点的指针一起跑
	var head = &YsfNode{1, nil}

	var cursorNode = head

	for i := 2; i <= n; i++ {
		temp := &YsfNode{i, nil}

		cursorNode.Number = i
		cursorNode.Next = temp
		cursorNode = temp
	}

	// 约瑟夫环形，必须将最后一个元素的指针指向head，这样才能形成环形
	cursorNode.Next = head

	return head
}

// 根据规则不断拆除节点，计算出最后剩余的节点即可
func CalcLastOneEle(head *YsfNode, startNum int, step int) int {
	var preNode *YsfNode = &YsfNode{}
	var cursorNode = head
	// 寻找起步元素对应的指针
	for cursorNode != cursorNode.Next {
		if cursorNode.Number == startNum {
			//fmt.Println("找到指定的起始元素：", startNum)
			break
		}
		cursorNode = cursorNode.Next
	}

	//  根据规则
	for cursorNode != cursorNode.Next {
		//  注意 ：  i <step ，就是step的起始元素包括开始元素本身，
		//  如果 i<= step  ，说明从开始元素的下一个元素算 step 的个数
		for i := 1; i < step; i++ {
			preNode = cursorNode
			cursorNode = cursorNode.Next
		}
		// 拆环，通过指针的重新指向修改环形队列元素
		preNode.Next = cursorNode.Next
		// 这里我们不主动调用 runtime.Gc 释放 cursorNode 指向的内存空间
		// 被删除的前一个元素的 next 重新指向下一个节点
		cursorNode = preNode.Next
	}
	return cursorNode.Number
}
